package datastructure.book.tujiesuanfa.queueastack.exercise.first;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 *  最大值队列，能在常数时间内检索到最大元素的队列
 *  所有方法时间复杂度均为O(1)
 */
public class Checkout {

    private final Queue<Integer> queue = new LinkedList<>();
    private final LinkedList<Integer> maxValueList = new LinkedList<>();

    public Checkout() {

    }
    /**
     * 空，返回-1
     */
    public int get_max() {
        if (maxValueList.isEmpty()) {
            return -1;
        }
        return maxValueList.peek();
    }

    public void add(int value) {
        queue.add(value);
        if (maxValueList.isEmpty()) {
            maxValueList.add(value);
            return;
        }
        Iterator<Integer> iterator = maxValueList.iterator();
        boolean flag = false;
        while (iterator.hasNext()) {
            if (flag) {
                iterator.next();
                iterator.remove();
                continue;
            }
            Integer next = iterator.next();
            if (value > next) {
                iterator.remove();
                flag = true;
            }
        }
        maxValueList.add(value);
    }
    /**
     * 空，返回-1
     */
    public int remove() {
        if (queue.isEmpty()) {
            return -1;
        }
        Integer poll = queue.poll();
        if (Objects.equals(maxValueList.peek(), poll)) {
            maxValueList.poll();
        }
        return poll;
    }
}
